import collections
class Solution(object):
    def recoverArray(self, n, sums):
        sums.sort()
        diff = 0
        if min(sums) < 0:
            diff = - min(sums)
        if diff:
            sums = [item + diff for item in sums]
        st = []
        i = 0
        while i < n:
            min_val = sums[1] - 0
            st.append(min_val)
            if min_val == 0:
                t = collections.Counter(sums)
                sums = []
                for key in t:
                    sums += [key] * (t[key] // 2) 
            else:
                m = len(sums)
                p = [0] * m
                index0 = 0
                index1 = 0
                new_sums = []
                while True:
                    while index0 < m and p[index0] == 1:
                        index0 += 1
                    if index0 == m:
                        break
                    p[index0] = 1
                    while sums[index1] - sums[index0] < min_val or p[index1] == 1:
                        index1 += 1
                    p[index1] = 1
                    index1 += 1
                    new_sums.append(sums[index0])
                sums = new_sums
            i += 1
        for val in range(2 ** n):
            t = 0
            for i in range(n):
                if (val >> i) & 1:
                    t += st[i]
            if t == diff:
                for i in range(n):
                    if (val >> i) & 1:
                        st[i] = - st[i]
                return st


data = Solution()
n = 3
sums = [-3,-2,-1,0,0,1,2,3]
print(data.recoverArray(n, sums))